package com.test.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author sujiafa
 * @date 2025/1/25
 */
public class n494_目标和 {

    // 用于存储已经计算过的子问题结果
    private Map<String, Integer> map = new HashMap<>();

    public int findTargetSumWays(int[] nums, int target) {
        return this.findTarget(nums, 0, 0, target);
    }

    /**
     * @param nums 输入的数组
     * @param index 当前遍历的索引
     * @param curSum 当前计算的结果
     * @param target 目标结果
     */
    private int findTarget(int[] nums, int index, int curSum, int target) {
        // 生成当前状态的唯一键
        String key = index + "_" + curSum;
        // 检查该状态是否已经计算过
        if (map.containsKey(key)) {
            return map.get(key);
        }

        // 当遍历完所有元素时
        if (index == nums.length) {
            if (curSum == target) {
                return 1;
            } else {
                return 0;
            }
        }

        // 递归计算两种情况：当前元素取负和取正
        int result = findTarget(nums, index + 1, curSum + nums[index], target)
                + findTarget(nums, index + 1, curSum - nums[index], target);
        // 将结果存入备忘录
        map.put(key, result);
        return result;
    }
}
